package com.ting.test.algorithms.查找算法.归并查找;

/**
 * 归并算法的核心思想是，
 * 将一个数组切分成两部分，分别排序后，再组合
 * 组合的时间复杂度是O(n)
 */
public class 非递归实现 {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 34, 6, 7, 8, 9, 0, 11, 21, 32, 12, 4, 5, 6, 8, 9, 18, 1};
//        int[] result = func(arr, 0, arr.length - 1);
        int[] result = func2(arr);
        System.out.println(result);
    }

    private static int[] func2(int[] arr) {
        if (null == arr || arr.length == 1) {
            return arr;
        }

        int N = arr.length;
        int step = 1;//步长
        while (step < N) {//步长不能大于N
            int L = 0;///L每次从0位置开始
            while (L < N) {
                if (step >= N - L) {
                    break;
                }

                int M = L + step - 1;
                int R = M + Math.min(step, N - M - 1);//不能超过N
                merge(arr, L, R, M);
                L = R + 1;//继续下一组
            }
            if (step > N / 2) {
                break;//防止溢出
            }
            step = step << 1;
        }

        return arr;

    }

    /**
     * 合并的思想是，
     * 一个元素只操作一次，谁小先放谁，一样大的，先放左边的
     *
     * @return
     */
    private static int[] merge(int[] arr, int L, int R, int M) {
        int[] help = new int[R - L + 1];
        int LIndex = L;
        int RIndex = M + 1;
        int index = 0;
        while (LIndex <= M && RIndex <= R) {
            help[index++] = arr[LIndex] <= arr[RIndex] ? arr[LIndex++] : arr[RIndex++];
        }
        //当程序走到这时，要么左边排完了，要么右边排完了，要么都拍完了，总之 后面两个循环，最多只可能执行一个
        while (LIndex <= M) {
            help[index++] = arr[LIndex++];
        }

        while (RIndex <= R) {
            help[index++] = arr[RIndex++];
        }

        for (int i = 0; i < help.length; i++) {
            arr[L++] = help[i];
        }
        return arr;
    }
}
